package linkedlist;

import java.util.HashSet;

/**
 * 链表反转
 *
 * @author shkstart
 * @create 2021-04-26 13:15
 */
public class ReverseList {

    static class ListNode {
        int val;
        ListNode next;


        public ListNode(int val, ListNode listNode) {
            this.val = val;
            this.next = listNode;
        }

    }

    public static void main(String[] args) {


        ListNode node5 = new ListNode(5, null);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
//        node5.next = node2;

//        ListNode recursion = recursion(node1);
//        while (true){
//            if(recursion==null){
//                break;
//            }
//          System.out.println(recursion.val);
//          recursion = recursion.next;
//        }

        boolean ring = hasCycle(node1);
        System.out.println(ring);

    }

    //反转
    public static ListNode recursion(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode new_head = recursion(head.next);
        head.next.next = head;
        head.next = null;
        return new_head;

    }
//给定一个链表，判断链表中是否有环。

    /**
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
     * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置
     * （索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
     * 注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
     * <p>
     * 如果链表中存在环，则返回 true 。 否则，返回 false
     */
    public static boolean ring(ListNode head) {

        if (head == null || head.next == null) {
            return false;
        }
        ListNode one = head;
        ListNode two = head.next;
        while (one != two) {
            if (two == null || one.next == null) {
                return false;
            }
            one = one.next;
            two = two.next.next;
        }


        return true;
    }
    public static boolean hasCycle(ListNode head){
        HashSet<ListNode> listNodes = new HashSet<>();
//        集合中添加相同的值会失败
         while (head !=null){
             if(!listNodes.add(head)){
                 return true;
             }
            head = head.next;

         }

        return false;
    }
}
